﻿//typedef struct Node {
//    int val;
//    struct Node* next;
//}Node;
//
//typedef struct Queue {
//    Node* head;
//    Node* tail;
//}Queue;
//
//bool QueueEmpty(Queue* Q) {
//    return Q->head == 0;
//}
//
//void QueuePush(Queue* Q, int x) {
//    Node* node = (Node*)malloc(sizeof(Node));
//    node->val = x;
//    node->next = 0;
//    if (!Q->head) {
//        Q->head = Q->tail = node;
//    }
//    else {
//        Q->tail->next = node;
//        Q->tail = node;
//    }
//}
//
//void QueuePop(Queue* Q) {
//    /*if (!Q->head) {
//        return;
//    }*/
//    Node* next = Q->head->next;
//    free(Q->head);
//    Q->head = next;
//}
//
//typedef struct {
//    Queue* Q1;
//    Queue* Q2;
//} MyStack;
//
//
//MyStack* myStackCreate() {
// //注意一点，在函数中来进行申请动态内存，不能本身直接申请，只能通过指针来解引用来申请，比如二级指针或指针访问的申请
//    MyStack* Stack = (MyStack*)malloc(sizeof(MyStack));
//    Stack->Q1 = (Queue*)malloc(sizeof(Queue));
//    Stack->Q1->head = Stack->Q1->tail = 0;
//    Stack->Q2 = (Queue*)malloc(sizeof(Queue));
//    Stack->Q2->head = Stack->Q2->tail = 0;
//    return Stack;
//}
//
//void myStackPush(MyStack* obj, int x) {
//    if (QueueEmpty(obj->Q1)) {
//        QueuePush(obj->Q2, x);
//    }
//    else {
//        QueuePush(obj->Q1, x);
//    }
//}
//
//int myStackPop(MyStack* obj) {
//    /*if (QueueEmpty(obj->Q1) && QueueEmpty(obj->Q2)) {
//        return;
//    }*/
//    if (QueueEmpty(obj->Q1)) {
//        while (obj->Q2->head->next) {
//            QueuePush(obj->Q1, obj->Q2->head->val);
//            QueuePop(obj->Q2);
//        }
//        int x = obj->Q2->head->val;
//        QueuePop(obj->Q2);
//        return x;
//    }
//    while (obj->Q1->head->next) {
//        QueuePush(obj->Q2, obj->Q1->head->val);
//        QueuePop(obj->Q1);
//    }
//    int x = obj->Q1->head->val;
//    QueuePop(obj->Q1);
//    return x;
//}
//
//int myStackTop(MyStack* obj) {
//    if (QueueEmpty(obj->Q1)) {
//        return obj->Q2->tail->val;
//    }
//    return obj->Q1->tail->val;
//}
//
//bool myStackEmpty(MyStack* obj) {
//    return QueueEmpty(obj->Q1) && QueueEmpty(obj->Q2);
//}
//
//void myStackFree(MyStack* obj) {
//    while (obj->Q1->head) {
//        QueuePop(obj->Q1);
//    }
//    while (obj->Q2->head) {
//        QueuePop(obj->Q2);
//    }
//    free(obj->Q1);
//    free(obj->Q2);
//    free(obj);
//}

//typedef struct Stack {
//    int* a;
//    int top;
//    int capacity;
//}Stack;
//
//void StackInit(Stack* S) {
//    S->a = (int*)malloc(sizeof(int) * 4);
//    memset(S->a, 0, sizeof(int) * 4);
//    S->capacity = 4;
//    S->top = -1;
//}
//
//bool StackEmpty(Stack* S) {
//    return S->top == -1;
//}
//
//void StackPush(Stack* S, int x) {
//    if (S->top == S->capacity - 1) {
//        S->a = (int*)realloc(S->a, sizeof(int) * S->capacity * 2);
//        S->capacity *= 2;
//    }
//    S->a[++S->top] = x;
//}
//
//void StackPop(Stack* S) {
//    if (S->top == -1) {
//        return;
//    }
//    S->top--;
//}
//
//typedef struct {
//    Stack* S1;
//    Stack* S2;
//} MyQueue;
//
//
//MyQueue* myQueueCreate() {
//    MyQueue* Q = (MyQueue*)malloc(sizeof(MyQueue));
//    Q->S1 = (Stack*)malloc(sizeof(Stack));
//    StackInit(Q->S1);
//    Q->S2 = (Stack*)malloc(sizeof(Stack));
//    StackInit(Q->S2);
//    return Q;
//}
//
//void myQueuePush(MyQueue* obj, int x) {
//    if (StackEmpty(obj->S1)) {
//        StackPush(obj->S2, x);
//    }
//    else {
//        StackPush(obj->S1, x);
//    }
//}
//
//int myQueuePop(MyQueue* obj) {
//    if (StackEmpty(obj->S1)) {
//        while (!StackEmpty(obj->S2)) {
//            StackPush(obj->S1, obj->S2->a[obj->S2->top]);
//            StackPop(obj->S2);
//        }
//        int x = obj->S1->a[obj->S1->top];
//        StackPop(obj->S1);
//        while (!StackEmpty(obj->S1)) {
//            StackPush(obj->S2, obj->S1->a[obj->S1->top]);
//            StackPop(obj->S1);
//        }
//        return x;
//    }
//    else {
//        while (!StackEmpty(obj->S1)) {
//            StackPush(obj->S2, obj->S1->a[obj->S1->top]);
//            StackPop(obj->S1);
//        }
//        int x = obj->S2->a[obj->S2->top];
//        StackPop(obj->S2);
//        while (!StackEmpty(obj->S2)) {
//            StackPush(obj->S1, obj->S2->a[obj->S2->top]);
//            StackPop(obj->S2);
//        }
//        return x;
//    }
//}
//
//int myQueuePeek(MyQueue* obj) {
//    if (StackEmpty(obj->S1)) {
//        while (!StackEmpty(obj->S2)) {
//            StackPush(obj->S1, obj->S2->a[obj->S2->top]);
//            StackPop(obj->S2);
//        }
//        int x = obj->S1->a[obj->S1->top];
//        while (!StackEmpty(obj->S1)) {
//            StackPush(obj->S2, obj->S1->a[obj->S1->top]);
//            StackPop(obj->S1);
//        }
//        return x;
//    }
//    else {
//        while (!StackEmpty(obj->S1)) {
//            StackPush(obj->S2, obj->S1->a[obj->S1->top]);
//            StackPop(obj->S1);
//        }
//        int x = obj->S2->a[obj->S2->top];
//        while (!StackEmpty(obj->S2)) {
//            StackPush(obj->S1, obj->S2->a[obj->S2->top]);
//            StackPop(obj->S2);
//        }
//        return x;
//    }
//}
//
//bool myQueueEmpty(MyQueue* obj) {
//    return StackEmpty(obj->S1) && StackEmpty(obj->S2);
//}
//
//void myQueueFree(MyQueue* obj) {
//    free(obj->S1->a);
//    free(obj->S2->a);
//    free(obj->S1);
//    free(obj->S2);
//    free(obj);
//}